home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / seqdemos / squeen.icl < prev    next >
Text File  |  1992-08-07  |  2KB  |  72 lines
  1. MODULE squeen;
  2.  
  3. <<
  4. The Queens Problem.
  5.  
  6. Or: How to put n queens on a n*n chessboard in such a way that they
  7. cannot attack each other.
  8.     
  9. The result of this program is the number of possible solutions for
  10. the queens problem for a certain boardsize together with one solution.
  11. When BoardSize is 8 the result will be: (92,[4,2,7,3,6,8,5,1]),
  12. which means the queens are on a4, b2, c7, d3, e6, f8, g5 and h1.
  13.  
  14. Strictness annotations are used at certain points, because that makes
  15. this program more than twice as fast (the strictness analyzer is not
  16. able to deduce this strictness information). However, other Clean programs
  17. for the Queens problem exist without strictness annotations added by the 
  18. programmer that are only 40% slower than this solution (lqueen.icl).
  19. >>
  20.  
  21. IMPORT deltaI;
  22.  
  23. MACRO
  24.  
  25.     BoardSize -> 8; == The size of the chessboard.
  26.  
  27. RULE
  28.  
  29. ==  Miscellaneous list functions.
  30.  
  31. ::  Length [x]      -> INT;
  32.     Length [hd|tl]  -> ++ (Length tl);
  33.     Length []       -> 0;
  34.  
  35. ::  Head [x]     -> x;
  36.     Head [hd|tl] -> hd;
  37.  
  38.  
  39. ==  Finding all solutions for the queens problem.
  40.  
  41.     
  42. ::  Queens INT [INT] [[INT]] -> [[INT]];
  43.     Queens row board boards -> [board | boards] , IF > row BoardSize
  44.                             -> TryCols BoardSize row board boards;
  45.  
  46. ::  TryCols INT INT [INT] [[INT]] -> [[INT]];
  47.     TryCols 0 row board boards -> boards;
  48.     TryCols col row board boards
  49.     ->  TryCols (-- col) row board queens , IF Save col 1 board
  50.     ->  TryCols (-- col) row board boards,
  51.         queens: Queens (++ row) [col | board] boards;
  52.  
  53. <<  The strictness analyzer can't derive strictness for the first and second
  54.     argument of Save, because they are not used in the first alternative
  55.     of that function. However, Save is strict in these arguments (in the
  56.     context of this program) and adding the strictness annotations speeds
  57.     up this program considerably.
  58. >>
  59. ::  Save !INT !INT [INT] -> BOOL;
  60.     Save  c1 rdiff [] -> TRUE;
  61.     Save  c1 rdiff [c2|cols]
  62.     ->  FALSE , IF = cdiff 0 || = cdiff rdiff || = cdiff (- 0 rdiff)
  63.     ->  Save c1 (++ rdiff) cols,
  64.         cdiff: - c1 c2;
  65.  
  66. <<  The Start Rule: Calculate the list of solutions, show the first
  67.     solution and the length of that list.
  68. >>
  69. ::  Start -> (INT,[INT]);
  70.     Start -> (Length solutions, Head solutions),
  71.              solutions: Queens 1 [] [];
  72.